Skip to main content

6. Shor's Algorithm

QFT​

在经典计算中，傅里叶变换用于将信号从时域转换到频域
量子傅里叶变换的数学定义

∣ψ⟩=∑j=0N−1aj∣j⟩⟶∣ϕ⟩=∑k=0N−1ϕk∣k⟩=1N∑k=0N−1∑j=0N−1aje2πijk/N∣k⟩|\psi\rangle = \sum_{j=0}^{N-1} a_j |j\rangle \longrightarrow |\phi\rangle = \sum_{k=0}^{N-1} \phi_k |k\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \sum_{j=0}^{N-1} a_j e^{2\pi i jk / N} |k\rangle

通过上述公式 QFT 把 基态转化为：

∣j⟩⟶1N∑k=0N−1e2πijk/N∣k⟩\ket{j} \longrightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk / N} \ket{k}

QFT 性质:

QFT†QFT=I.\text{QFT}^\dagger \text{QFT} = I.

Inverse Quantum Fourier Transform​

IQFT does the reverse:

1N∑k=0N−1e2πijk/N∣k⟩⟶∣j⟩\frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk / N} \ket{k} \longrightarrow \ket{j}

Quantum Phase Estimation, QPE​

量子相位估计算法的主要目标是：给定一个酉算符 U 及其本征态 ∣ψ⟩\ket{\psi} 精确地估计对应的本征值的相位 θ\theta

Shor’s algorithm 的整体思路​

Shor算法将整数因数分解问题转化为周期发现问题。具体步骤如下:

  1. 随机选择一个整数 aa , 满足 1<a<n1<a<n
    • 如果 gcd(a,N)≠1(a,N) \not= 1 , 则a和NN不互质，直接得到一个因数
    • 否则， 下一步
  2. 找到函数 f(x)=axf(x) = a^x mod NN 最小正周期 rr
    • 也就是找到最小的正整数 rr ,使得 ar≡1a^r \equiv 1 mod NN
  3. 利用周期 rr 来找到 NN 的因数

    • 如果 rr 是偶数， 且 ar/2≢−1a^ {r/2} \not \equiv -1 mod NN , 则：

      gcd(ar/2±1,N)(a^{r/2} \pm 1 , N) 将给出N的非平凡因数